package com.mzy.linear_struct.面试150题;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/15/上午1:50
 * @Description:
 */
public class Pro121买卖股票的最佳时机 {
    /*    public int maxProfit(int[] prices) {
            // 定义dp数组
            // dp[i][j]    i 表示第i天， j表示是否持有股票
            // dp[i][0]    表示第i天持有股票
            // dp[i][1]    表示第i天不持有股票    有可能之前从来没有买过，也有可能买过又卖出了
            int[][] dp = new int[prices.length][2];

            // 初始状态
            dp[0][0] = prices[0];
            dp[0][1] = 0;
            System.out.println(dp[0][0] + " " + dp[0][1]);

            for (int i = 1; i < dp.length; i++) {
                dp[i][0] = Math.min(dp[i - 1][0], prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], prices[i] - dp[i - 1][0]);

                System.out.println(dp[i][0] + " " + dp[i][1]);
            }
            return dp[prices.length - 1][1];
        }*/
    /*
    public int maxProfit(int[] prices) {
        int ans = 0;

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {

            min = Math.min(prices[i], min);
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }
    */

    public static void main(String[] args) {
        System.out.println(new Pro121买卖股票的最佳时机().maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }

/*    private int maxProfit(int[] prices) {
        // dp[i][0] 表示i天持有股票
        // dp[i][1] 表示i天不持有股票   可能卖出，可能没买

        int[][] dp = new int[prices.length][2];

        // dp[i][0] = Math.min(dp[i - 1][0], prices[i])
        // dp[i][1] = Math.max(dp[i - 1][1], prices[i] - dp[i -1][0])
        dp[0][0] = prices[0];
        dp[0][1] = 0;
        System.out.println("dp[0][0]  " + dp[0][0] + "  dp[0][1]  " +dp[0][1]);
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.min(dp[i - 1][0], prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] - dp[i - 1][0]);
            System.out.println("dp["+i+"][0]  " + dp[i][0] + "  dp["+i+"][1]  " +dp[i][1]);
        }
        return dp[prices.length - 1][1];
    }*/

    private int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            ans = Math.max(prices[i] - min, ans);
            System.out.println(ans);
        }
        return ans;
    }
}
